package com.yun.datastructure.graph;

import com.yun.datastructure.graph.domain.Edge;
import com.yun.datastructure.graph.domain.Vertex;

import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 单源最短路径算法
 * 利用优先级队列实现
 */
public class DijkstraPriorityQueue {
    private static void dijkstra(List<Vertex> graph, Vertex source) {
        PriorityQueue<Vertex> queue=new PriorityQueue<>(Comparator.comparingInt(v->v.dist));
        source.dist = 0;
        for (Vertex v : graph) {
            queue.offer(v);
        }
        while (!queue.isEmpty()) {
            //3.选取当前顶点
            Vertex curr = queue.peek();
            //4.更新当前顶点邻居距离
            if(!curr.visited){
                updateNeighbourDist(curr,queue);
                curr.visited=true;
            }
            //5.移除当前顶点
            queue.poll();
        }
        for (Vertex v : graph) {
            System.out.println(v.name + " " + v.dist+" "+(v.prev!=null?v.prev.name:"null"));
        }
    }

    private static void updateNeighbourDist(Vertex curr,PriorityQueue<Vertex> queue) {
        for (Edge edge : curr.edges) {
            Vertex n = edge.linked;
            if (!n.visited) {
                int dist = curr.dist + edge.weight;
                if (dist < n.dist) {
                    n.dist = dist;
                    n.prev = curr;
                    queue.offer(n);
                }
            }
        }
    }
}
